
"""
NC68 跳台阶
https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=117&&tqId=37764&&companyId=239&rp=1&ru=/company/home/code/239&qru=/ta/job-code-high/question-ranking
"""

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param number int整型
# @return int整型
#


class Solution:
    memo = {}

    def method1(self, number: int) -> int:
        """
        递归+记忆化搜索
        """
        if number <= 1:
            return 1

        if number == 2:
            return 2

        if number not in self.memo:
            self.memo[number] = self.method1(number-1) + self.method1(number-2)

        return self.memo[number]

    def method2(self, number: int) -> int:
        """
        递推
        """
        lst = [0]*(number+1)
        lst[0], lst[1] = 1, 1

        for i in range(2, number+1):
            lst[i] = lst[i-1] + lst[i-2]

        return lst[number]

    def jumpFloor(self, number: int) -> int:
        # write code here
        assert number >= 0, "number can not be a negative number"
        return self.method2(number)


def test():
    obj = Solution()
    res = obj.jumpFloor(7)
    print(res)


if __name__ == "__main__":
    test()
